package org.example.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 本实现使用数组最后一个元素作为主元（比较对象）
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{8, 7, 3, 2, 5, 9, 4, 20, 13, 45, 91, 88};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
        doSort(arr, 0, arr.length - 1);
    }

    public static void doSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivot = partitionUseArrEnd(arr, start, end);
            //递归调用doSort
            doSort(arr, start, pivot - 1);
            doSort(arr, pivot + 1, end);
        }
    }

    //<=i的区域维护为比主元小的区域；初始i=-1
    //>i && <=j的区域为比主元大的区域;
    //>j && <end的区域为未比较区域
    public static int partitionUseArrEnd(int[] arr, int start, int end) {
        //使用数组最后一个元素作为主元
        int compare = arr[end];
        int i = start - 1;
        for (int j = i+1; j < end; j++) {
            if (arr[j] <= compare) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, ++i, end);
        return i;
    }

    //int[] arr = new int[]{8, 7, 3, 2, 5, 9, 4};
    public static int partitionUseArrStart(int[] arr, int start, int end) {
        //使用首个元素作为主元
        int compare = arr[start];
        int i = start;
        for (int j = i+1; j<=end; j++) {
            if (arr[j] <= compare) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, start, i);
        return i;
    }

    public static int partitionUseRandom(int[] arr, int start, int end) {
        //使用随机元素作为主元
        Random random = new Random();
        int randomIndex = random.nextInt(end - start + 1) + start;
        swap(arr, end, randomIndex);
        return partitionUseArrEnd(arr, start, end);
    }

    //交换两个数组元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}